/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-09
 * Time: 20:16
 */
public class MyHeap {

    //向下调整_建小根堆
    public void siftDownToMinHeap(int[] arr,int parent) {
        int child = 2*parent + 1;
        int size = arr.length;

        while (child < size) {
            //若右孩子存在,比较左右孩子的大小
            if (child + 1 < size && arr[child + 1] < arr[child]) {
                child = child + 1;
            }

            //如果child比parent的值还小，那么交换，符合小根堆
            if (arr[child] < arr[parent]) {
                swap(arr,child,parent);
                //parent继续向下走，防止这次交换后破坏堆结构
                parent = child;
                child = 2*parent + 1;
            }else {
                //符合堆结构就跳出循环，避免不必要的循环
                break;
            }
        }
    }

    //交换两个数
    private void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //创建小根堆
    public void createMinHeap(int[] arr) {
        //最后一个叶子结点的下标
        int child = arr.length - 1;
        //当parent == 0时，说明parent走到了树的根结点
        for(int parent = (child - 1)/2; parent >= 0; parent--) {
            //对每个非叶子结点进行向下调整
            siftDownToMinHeap(arr,parent);
        }
    }

    //创建大根堆
    public void createMaxHeap(int[] arr) {
        //最后一个叶子结点的下标
        int child = arr.length - 1;
        //当parent == 0时，说明parent走到了树的根结点
        for(int parent = (child - 1)/2; parent >= 0; parent--) {
            //对每个非叶子结点进行向下调整
            siftDownToMaxHeap(arr,parent);
        }
    }

    //向下调整_建大根堆
    public void siftDownToMaxHeap(int[] arr,int parent) {
        int child = 2*parent + 1;
        int size = arr.length;

        while (child < size) {
            //若右孩子存在,比较左右孩子的大小
            if (child + 1 < size && arr[child + 1] > arr[child]) {
                child = child + 1;
            }

            //如果child比parent的值还大，那么交换，符合大根堆
            if (arr[child] > arr[parent]) {
                swap(arr,child,parent);
                //parent继续向下走，防止这次交换后破坏堆结构
                parent = child;
                child = 2*parent + 1;
            }else {
                //符合堆结构就跳出循环，避免不必要的循环
                break;
            }
        }
    }
}
